package com.sheng.leetcode.year2022.month09.day11;

import org.junit.Test;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.stream.IntStream;

/**
 * @author liusheng
 * @date 2022/09/13
 *<p>
 * 857. 雇佣 K 名工人的最低成本<p>
 *<p>
 * 有 n名工人。给定两个数组quality和wage，其中，quality[i]表示第i名工人的工作质量，其最低期望工资为wage[i]。<p>
 * 现在我们想雇佣k名工人组成一个工资组。在雇佣一组 k名工人时，我们必须按照下述规则向他们支付工资：<p>
 * 对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。<p>
 * 工资组中的每名工人至少应当得到他们的最低期望工资。<p>
 * 给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额。在实际答案的10-5以内的答案将被接受。。<p>
 *<p>
 * 示例 1：<p>
 * 输入： quality = [10,20,5], wage = [70,50,30], k = 2<p>
 * 输出： 105.00000<p>
 * 解释： 我们向 0 号工人支付 70，向 2 号工人支付 35。<p>
 *<p>
 * 示例 2：<p>
 * 输入： quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3<p>
 * 输出： 30.66667<p>
 * 解释： 我们向 0 号工人支付 4，向 2 号和 3 号分别支付 13.33333。<p>
 *<p>
 * 提示：<p>
 *<p>
 * n == quality.length == wage.length<p>
 * 1 <= k <= n <= 104<p>
 * 1 <= quality[i], wage[i] <= 104<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/minimum-cost-to-hire-k-workers">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode0857 {

    @Test
    public void test01() {
        int[] quality = {10,20,5}, wage = {70,50,30};
        int k = 2;
//        int[] quality = {3,1,10,10,1}, wage = {4,8,2,2,7};
//        int k = 3;
        System.out.println(new Solution().mincostToHireWorkers(quality, wage, k));
    }
}
class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        // 思路：首先选择你要用的工人是哪几位，按照选择的工人中的最高薪资为标准，按比例分配其他工人的工资
        // 工作质量和工资相乘，然后除以标准基数，则为应该支付的最低工资
        int n = quality.length;
        // 创建一个数组长度为n的数组，sort代表员工的编号
        Integer[] sort = IntStream.range(0, n).boxed().toArray(Integer[]::new);
        // 根据质量比进行排序
        // 按照以下排序规则 wage[i] / quality[i] >  wage[j] / quality[j]  ->  wage[i] * quality[j] >  wage[j] * quality[i]
        Arrays.sort(sort, (o1, o2) -> wage[o1] * quality[o2] - wage[o2] * quality[o1]);
        // 总的结果
        double res = 1e9;
        // 总的质量
        double totalq = 0.0;
        // 创建优先级队列
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        // 取k个人的质量总和
        for (int i = 0; i < n; i++) {
            int idx = sort[i];
            // 取前k-1个人 性价比高的 得到质量总和
            totalq += quality[idx];
            // 将当前质量加入优先级队列，质量低的优先
            pq.offer(quality[idx]);
            if (i >= k - 1) {
                // 剩余一个对比花费最少
                res = Math.min(res, ((double) wage[idx] / quality[idx]) * totalq);
                totalq -= pq.poll();
            }
        }
        return res;
    }
}

// https://blog.csdn.net/qq_35530042/article/details/126802862?spm=1001.2101.3001.6650.2&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EOPENSEARCH%7Edefault-2-126802862-blog-126803753.pc_relevant_multi_platform_whitelistv4eslandingctr2&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EOPENSEARCH%7Edefault-2-126802862-blog-126803753.pc_relevant_multi_platform_whitelistv4eslandingctr2&utm_relevant_index=3
//public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
//    // 对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
//    //工资组中的每名工人至少应当得到他们的最低期望工资。
//    // 首先我们得用公式推导：
//    // k个人：1-k ,某个人是i
//    // 对应的质量：q[i],对应的工资期待是w[i]
//    // 实际的收入是和质量成比例的，也就是假定比例是t[i] = sum(q[1]...q[k])/k
//    // 那么实际的收入就比例乘自身质量：r[i] = t[i]*q[i]，题目中，必须不低于最低期望，所以r[i] >= w[i]
//    // 综合可以得到 t[i]*q[i]>=w[i] 等价于 t[i] >= w[i]/q[i]
//    // 而题目是为了 找k个人，给最少的钱，质量不看重；所以只需要找比例 t[i] 最大的k个人就好了
//    // 第一步要算出k个人，每人的质量比就好了 w[i]/q[i] > w[j]/q[j]
//    // 所以才会有w[i]*q[j]-w[j]*q[i] 的排序,还可以避免精度问题
//    Integer[] sort = IntStream.range(0, quality.length).boxed().toArray(Integer[]::new);
//    Arrays.sort(sort, (l, r) -> quality[r] * wage[l] - quality[l] * wage[r]);
//    // 得到了质量比的排序后，有三个变量，质量、花费、最低期望：所以锁定第k人质量最高情况，k-1人质量越低，花费工资越少，然后再对比第k人的质量情况
//    // 总的结果
//    double res = 1e9;
//    // 总的质量
//    double totalq = 0.0;
//    // 创建优先级队列
//    PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
//    // 取k个人的质量总和
//    for (int i = 0; i < sort.length; i++) {
//        int idx = sort[i];
//        // 取前k-1个人 性价比高的 得到质量总和
//        totalq += quality[idx];
//        // 将当前质量加入优先级队列，质量低的优先
//        pq.offer(quality[idx]);
//        if (i >= k - 1) {
//            // 剩余一个对比花费最少
//            res = Math.min(res, ((double) wage[idx] / quality[idx]) * totalq);
//            totalq -= pq.poll();
//        }
//    }
//    return res;
//}

// https://blog.csdn.net/qq_42467009/article/details/126803753
